package oj.oj_niuke_链表中倒数第k个结点;

import oj.ListNode;

/**
 * 链表中倒数第k个结点
 * https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
 */

//时间复杂度：O(n)
//空间复杂度：O(1)
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        int size =0;
        // 1) 先求出链表的元素（结点）个数
        for( ListNode cur=head;cur!=null;cur=cur.next){
            size++;
        }
        // 2) 求出从头节点向后跳 x 步
        int step=size-k;
        // 3) 从头结点开始向后跳
        if(step>=0){
            for(int i=0;i<step;i++){
                head=head.next;
            }
        }
        else{
            head=null;
        }
        return head;// 目前指向倒数第 k 个结点
    }
}
